﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;

namespace FindPath
{
    public partial class frmMain : Form
    {
        private Dictionary<int, Place> listPlaces = new Dictionary<int, Place>();
        private List<int> traversedPlace = new List<int>(); 
        public frmMain()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            loadWarpFile();
        }

        private void loadWarpFile()
        {
            if (File.Exists(Constants.WARP_CONFIG))
            {
                string[] fileLines = File.ReadAllLines(Constants.WARP_CONFIG);
                foreach (string eachLine in fileLines)
                {
                    string[] lineEles = eachLine.Split('\t');
                    if (lineEles[0] == "1")
                    {
                        int mapId = int.Parse(lineEles[1]);
                        int warpId = int.Parse(lineEles[2]);
                        int childMapId = int.Parse(lineEles[3]);
                        Place parentMap = null;

                        if (!listPlaces.ContainsKey(mapId))
                        {
                            parentMap = new Place { mapID = mapId, name = "", parent = new KeyValuePair<int,Place>(-1, null), child = new Dictionary<int, Place>() };
                            listPlaces.Add(mapId, parentMap);
                        }
                        else
                        {
                            parentMap = listPlaces[mapId];
                        }
                        Place newChild = null;
                        if (!listPlaces.ContainsKey(childMapId))
                        {
                            newChild = new Place { mapID = childMapId, name = "", parent = new KeyValuePair<int,Place>(-1, null), child = new Dictionary<int, Place>() };
                            listPlaces.Add(childMapId, newChild);
                        }
                        else
                        {
                            newChild = listPlaces[childMapId];
                        }
                        if (!parentMap.child.ContainsKey(warpId))
                        {
                            parentMap.child.Add(warpId, newChild);
                        }

                    }
                    else if (lineEles[0] == "2")
                    {
                        int mapId = int.Parse(lineEles[1]);
                        String mapName = lineEles[2];
                        if (listPlaces.ContainsKey(mapId))
                        {
                            Place place = listPlaces[mapId];
                            place.name = mapName;
                        }
                    }
                }
                buildWarpTree();
            }
            else
            {
                rtcResult.Text = "FILE NOT FOUND";
            }
        }

        private void buildWarpTree()
        {
            traversedPlace.Clear();
            trvWarp.Nodes.Clear();
            if (listPlaces.ContainsKey(12000))
            {
                Place startPoint = listPlaces[12000];
                traversedPlace.Add(12000);
                TreeNode rootNode = new TreeNode(startPoint.name + "-" + startPoint.mapID, buildChildNode(startPoint));
                trvWarp.Nodes.Add(rootNode);
            }
        }
        private TreeNode[] buildChildNode(Place parentData)
        {
            List<TreeNode> listNodes = new List<TreeNode>();
            traversedPlace.Add(parentData.mapID);
            foreach (KeyValuePair<int, Place> pair in parentData.child)
            {
                if (!traversedPlace.Contains(pair.Value.mapID))
                {
                    listNodes.Add(new TreeNode("[" + pair.Key + "] - " + pair.Value.mapID + " - " + pair.Value.name, buildChildNode(pair.Value)));
                }
            }
            return listNodes.ToArray();
        }

        private Place findPathBFS(int startId, int endId)
        {
            
            Place result = null;
            if (listPlaces.ContainsKey(startId) && listPlaces.ContainsKey(endId))
            {
                Place startPoint = listPlaces[startId];
                Queue<Place> traverseQueue = new Queue<Place>();
                traverseQueue.Enqueue(startPoint);
                while (traverseQueue.Count > 0)
                {
                    Place place = traverseQueue.Dequeue();
                    traversedPlace.Add(place.mapID);
                    foreach (KeyValuePair<int, Place> pair in place.child) {
                        if (pair.Value.mapID == endId)
                        {
                            pair.Value.parent = new KeyValuePair<int, Place>(pair.Key, place);
                            return pair.Value;
                        }
                        if (!traversedPlace.Contains(pair.Value.mapID))
                        {
                            pair.Value.parent = new KeyValuePair<int, Place>(pair.Key, place);
                            traverseQueue.Enqueue(pair.Value);
                        }
                    }
                    
                }
            }
            
            return result;
        }

        private Stack<string> findPathDFS(int startId, int endId)
        {
            
            Stack<string> result = new Stack<string>();

            if (listPlaces.ContainsKey(startId) && listPlaces.ContainsKey(endId))
            {
                traversedPlace.Add(startId);
                if (startId == endId)
                {
                    result.Push(endId + "\n");
                    return result;
                }
                else
                {
                    Place startPoint = listPlaces[startId];
                    Place endPoint = listPlaces[endId];
                    if (startPoint.child != null && startPoint.child.Count > 0)
                    {
                        foreach (KeyValuePair<int, Place> pair in startPoint.child)
                        {
                            if (pair.Value.mapID == endId)
                            {
                                result.Push(startId + "[" + pair.Key + "] => " + endId + "\n");
                                return result;
                            }
                        }
                        foreach (KeyValuePair<int, Place> pair in startPoint.child)
                        {
                            if (!traversedPlace.Contains(pair.Value.mapID))
                            {
                                Stack<String> path = findPathDFS(pair.Value.mapID, endId);
                                if (path != null && path.Count > 0)
                                {
                                    path.Push(startId + "[" + pair.Key + "] => " + pair.Value.mapID + "\n");
                                    result = path;
                                    return result;
                                }
                                else
                                {
                                    traversedPlace.Remove(pair.Value.mapID);
                                }
                            }

                        }
                    }
                }
            }
            else
            {
                result = null;
            }
            return result;
        }

        private void btnFind_Click(object sender, EventArgs e)
        {
            traversedPlace.Clear();
            int startId = int.Parse(txtStart.Text);
            int endId = int.Parse(txtDest.Text);
            Stack<String> path = findPathDFS(startId, endId);
            rtcResult.Clear();
            rtcResult.Text = "DONE\n";
            
            if (path != null && path.Count > 0) {
                foreach (String step in path)
                {
                    rtcResult.Text += step;
                }
                
            } else {
                rtcResult.Text += " PATH NOT FOUND";
            }
        }

        private void btnFindBFS_Click(object sender, EventArgs e)
        {
            traversedPlace.Clear();
            foreach (Place place in listPlaces.Values)
            {
                place.parent = new KeyValuePair<int, Place>(-1, null);
            }
            int startId = int.Parse(txtStart.Text);
            int endId = int.Parse(txtDest.Text);
            Place endPoint = findPathBFS(startId, endId);
            rtcResult.Clear();
            rtcResult.Text = "DONE\n";

            if (endPoint != null)
            {
                Stack<string> tracePath = new Stack<string>();
                Place currentPoint = endPoint;
                while (currentPoint != null) {

                    if (currentPoint.parent.Value != null)
                    {
                        tracePath.Push(currentPoint.parent.Value.mapID + " [" + currentPoint.parent.Key + "] => " + currentPoint.mapID + "\n");
                    } 
                    currentPoint = currentPoint.parent.Value;
                    
                }
                foreach (String step in tracePath)
                {
                    rtcResult.Text += step;
                }
            }
            else
            {
                rtcResult.Text += " PATH NOT FOUND";
            }
            
        }

    }
}
